class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

public class treeToDoublyList {
    Node head, pre;

    public Node _treeToDoublyList(Node root) {
        // 二叉搜索树 中序遍历 递增
        if (root == null)
            return root;
        inorder(root);

        head.left = pre;
        pre.right = head;
        return head;

    }

    public void inorder(Node root) {
        if (root == null)
            return;
        // 左边树
        inorder(root.left);
        // 操作
        if (pre == null)
            head = root;
        else if (pre != null)
            pre.right = root;
        // 再让当前节点的左指针指向父节点，也就连成了双向链表
        root.left = pre;
        // 保存当前节点，用于下层递归创建
        pre = root;
        // 右边树
        inorder(root.right);

    }
}
